package leetcode.day_2021_04_12_2021_04_18;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 93. 复原 IP 地址
 * https://leetcode-cn.com/problems/restore-ip-addresses/solution/java-biao-zhun-hui-su-fei-chang-rong-yi-6hg9v/
 */
public class LeetCode0093 {
    static List<String> result;
    public static List<String> restoreIpAddresses(String s) {
        result = new LinkedList<>();
        if (s.length()<4 || s.length()>12) {
            return result;
        }
        dfs(s, 0, 0, new StringBuilder(), 0);
        return result;
    }

    public static void dfs(String s, int start, int end, StringBuilder sb, int times) {
        if (times > 5) {
            return;
        }
        if (times==5 && start==s.length() && start+1==end) {
            result.add(sb.toString());
            return;
        }
        if (end > s.length()) {
            return;
        }
        if (end-start>1 && s.charAt(start)=='0'){
            return;
        }
        if (end>start && Integer.parseInt(s.substring(start, end))>255) {
            return;
        }

        for (int i=1; i<=3; i++) {
            sb.append(s.substring(start, end));
            if (times>0 && times<=3) {
                sb.append(".");
            }
            dfs(s, end, end+i, sb, times+1);
            if (times>0 && times<=3) {
                sb.deleteCharAt(sb.length()-1);
            }
            sb.delete(sb.length() - (end-start), sb.length());
        }
    }

    public static void main(String[] args) {
        restoreIpAddresses("25525511135");
        System.out.println(result);
    }
}
